package com.arron.algorithm.leetcodetop100.回溯.排列and组合and子集;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 组合总和II {


    List<List<Integer>> allSubList;
    int sum;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        allSubList = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();
        Arrays.sort(candidates);
        subsets(candidates,subList,0,target);
        return allSubList;
    }

    public void subsets(int[] candidates,List<Integer> subList,int start,int target){

        if (sum == target){
            allSubList.add(new ArrayList<>(subList));
            return;
        }

        if (sum > target){
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (i>start && candidates[i] == candidates[i-1]) {
                continue;
            }
            subList.add(candidates[i]);
            sum = sum + candidates[i];
            subsets(candidates,subList,i+1,target);
            sum = sum - candidates[i];
            subList.remove(subList.size()-1);
        }

    }

    public static void main(String[] args) {
        组合总和II  combinationSum2= new 组合总和II();
        int[] nums = {10,1,2,7,6,5};
        System.out.println(combinationSum2.combinationSum2(nums, 8));

    }


}
